package study.datastructure.order.sort;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2024-07-10 14:41
 */

import com.sun.org.apache.bcel.internal.generic.SWAP;
import com.sun.org.apache.xerces.internal.dom.PSVIAttrNSImpl;

import java.util.Arrays;

/**
 2024/7/10,
 */

//堆排序
public class HeapSort {
    public static void heapSort(int[] array){
        int n=array.length;

        for(int i=n/2-1; i>=0; i--){
            //构建最大堆， 它们都是有孩子的节点
            heapAjust(array,n,i);
        }

        //调整最大堆
        for (int i = n-1; i >0 ; i--) {
            //交换 从数组末尾取出的最小值到数组头部array[0]
            int swap=array[i];
            array[i]=array[0];
            array[0]=swap;

            heapAjust(array,i,0);
        }


    }

    private static void heapAjust(int[] array, int n, int i) {
        int largest=i;
        int left=2*i+1;
        int right=2*i+2;

        while (left<n){
            if (left<n && array[left]>array[largest]){
                largest=left;
            }
            if (right<n && array[right]>array[largest]){
                largest=right;
            }

            //如果最大元素不是当前节点, 则进行交换
            if(largest!=i){
                int swap=array[i];
                array[i]=array[largest];
                array[largest]=swap;

                //继续调整子树
                i=largest;
                left=2*i+1;
                right=2*i+2;

            }else {
                //没有交换的节点 直接退出
                break;
            }

        }
    }

    //最好 最坏 平均时间复杂度均为nlogn
//由于初始构建堆所需的比较次数比较多，因此，它并不适合待排序序列个数较少的情况
    public static void main(String[] args) {
            int[] arr = {10, 3, 7, 1, 9, 6};
            heapSort(arr);
            System.out.println(Arrays.toString(arr));
    }

}
